#define _CRT_SECURE_NO_WARNINGS  1
#pragma warning(disable:6031)
//https://leetcode.cn/contest/weekly-contest-398/problems/special-array-ii/

class Solution {
public:
    vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries)
    {
        int n = nums.size(), len = queries.size();
        vector<bool> answer(len);
        vector<int> hash(n, 1);

        int next = nums[n - 1] % 2, count = 1;
        for (int i = n - 2; i >= 0; --i)
        {
            if ((nums[i] % 2) == next)
                count = 1;
            else
                ++count;

            hash[i] = count;

            next = nums[i] % 2;
        }

        for (int i = 0; i < len; i++)
        {
            int wid = queries[i][1] - queries[i][0] + 1;

            int index = queries[i][0];
            if (hash[index] < wid) answer[i] = false;
            else answer[i] = true;
        }

        return answer;
    }
};